//class Solution {
//public:
//    bool evaluateTree(TreeNode* root) {
//        if (root->left == nullptr && root->right == nullptr) return root->val ? true : false;
//        bool left = evaluateTree(root->left);
//        bool right = evaluateTree(root->right);
//        return root->val == 2 ? (left | right) : (left & right);
//    }
//};




//class Solution {
//public:
//    int sum = 0;
//    int sumNumbers(TreeNode* root) {
//        dfs(root, 0);
//        return sum;
//    }
//
//    void dfs(TreeNode* root, int prevSum)
//    {
//        prevSum = prevSum * 10 + root->val;
//        if (root->left == nullptr && root->right == nullptr)
//        {
//            sum += prevSum;
//            return;
//        }
//
//
//        if (root->left)
//            dfs(root->left, prevSum);
//        if (root->right)
//            dfs(root->right, prevSum);
//    }
//};





//class Solution {
//public:
//    TreeNode* pruneTree(TreeNode* root) {
//        if (root->left == nullptr && root->right == nullptr)
//            return root->val ? root : nullptr;
//        if (root->left)
//            root->left = pruneTree(root->left);
//        if (root->right)
//            root->right = pruneTree(root->right);
//        return (root->left || root->right || root->val == 1) ? root : nullptr;
//    }
//};

//class Solution {
//public:
//    TreeNode* pruneTree(TreeNode* root) {
//        if (root == nullptr) return root;
//        root->left = pruneTree(root->left);
//        root->right = pruneTree(root->right);
//        if (root->left == nullptr && root->right == nullptr && root->val == 0)
//        {
//            delete root;
//            root = nullptr;
//        }
//        return root;
//    }
//};





//class Solution {
//public:
//    long long Prev = LLONG_MIN;
//    bool isValidBST(TreeNode* root) {
//        if (root == nullptr) return true;
//        if (isValidBST(root->left) == false) return false;
//        if (root->val <= Prev) return false;
//        Prev = root->val;
//        return isValidBST(root->right);
//    }
//};




//class Solution {
//public:
//    int target = 0, count = 0;
//    int kthSmallest(TreeNode* root, int k) {
//        count = k;
//        dfs(root);
//        return target;
//    }
//
//    void dfs(TreeNode* root)
//    {
//        if (root == nullptr) return;
//        dfs(root->left);
//        if (count == 1)
//            target = root->val;
//        count--;
//        dfs(root->right);
//    }
//};




//class Solution {
//public:
//    vector<string> ret;
//    vector<string> binaryTreePaths(TreeNode* root) {
//        string path;
//        dfs(root, path);
//        return ret;
//    }
//    void dfs(TreeNode* root, string path)
//    {
//        path += to_string(root->val);
//        if (root->left == nullptr && root->right == nullptr)
//        {
//            ret.push_back(path);
//        }
//
//        path += "->";
//        if (root->left)
//            dfs(root->left, path);
//        if (root->right)
//            dfs(root->right, path);
//    }
//};



//class Solution {
//public:
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    bool vis[60][60];
//    int m, n, target;
//    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
//        m = image.size(), n = image[0].size(), target = image[sr][sc];
//        if (target == color) return image;
//        dfs(image, sr, sc, color);
//        return image;
//    }
//
//    void dfs(vector<vector<int>>& image, int sr, int sc, int color)
//    {
//        if (vis[sr][sc]) return;
//        image[sr][sc] = color, vis[sr][sc] = true;
//        for (int i = 0; i < 4; i++)
//        {
//            int x = sr + dx[i], y = sc + dy[i];
//            if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false && image[x][y] == target)
//                dfs(image, x, y, color);
//        }
//    }
//};




//class Solution {
//public:
//    int ret = 0;
//    int m, n;
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    bool vis[310][310];
//    int numIslands(vector<vector<char>>& grid) {
//        m = grid.size(), n = grid[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == '1' && vis[i][j] == false)
//                {
//                    ret++;
//                    dfs(grid, i, j);
//                }
//            }
//        }
//        return ret;
//    }
//
//    void dfs(vector<vector<char>>& grid, int i, int j)
//    {
//        vis[i][j] = true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + i, y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false && grid[x][y] == '1')
//                dfs(grid, x, y);
//        }
//    }
//};




//class Solution {
//public:
//    int m, n, ret = 0;
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    bool vis[60][60];
//    int maxAreaOfIsland(vector<vector<int>>& grid) {
//        m = grid.size(), n = grid[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == 1 && vis[i][j] == false)
//                    ret = max(ret, dfs(grid, i, j));
//            }
//        }
//        return ret;
//    }
//
//
//    int dfs(vector<vector<int>>& grid, int i, int j)
//    {
//        int ret = 1;
//        vis[i][j] = true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + i, y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && vis[x][y] == false)
//                ret += dfs(grid, x, y);
//        }
//        return ret;
//    }
//};




//class Solution {
//public:
//    int m, n;
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    void solve(vector<vector<char>>& board) {
//        m = board.size(), n = board[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            if (board[i][0] == 'O')
//                dfs(board, i, 0);
//            if (board[i][n - 1] == 'O')
//                dfs(board, i, n - 1);
//        }
//
//        for (int j = 0; j < n; j++)
//        {
//            if (board[0][j] == 'O')
//                dfs(board, 0, j);
//            if (board[m - 1][j] == 'O')
//                dfs(board, m - 1, j);
//        }
//
//
//        for (int i = 0; i < m; i++)
//            for (int j = 0; j < n; j++)
//                if (board[i][j] == '.')
//                    board[i][j] = 'O';
//                else if (board[i][j] == 'O')
//                    board[i][j] = 'X';
//    }
//
//    void dfs(vector<vector<char>>& board, int i, int j)
//    {
//        board[i][j] = '.';
//        for (int k = 0; k < 4; k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
//                dfs(board, x, y);
//        }
//    }
//};




//class Solution {
//public:
//    int m, n;
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
//        m = heights.size(), n = heights[0].size();
//        vector<vector<bool>> atl(m, vector<bool>(n)), pac = atl;
//        for (int i = 0; i < m; i++)
//        {
//            dfs(heights, i, 0, pac);
//            dfs(heights, i, n - 1, atl);
//        }
//
//        for (int j = 0; j < n; j++)
//        {
//            dfs(heights, 0, j, pac);
//            dfs(heights, m - 1, j, atl);
//        }
//
//        vector<vector<int>> ret;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (pac[i][j] && atl[i][j])
//                    ret.push_back({ i, j });
//            }
//        }
//        return ret;
//    }
//
//    void dfs(vector<vector<int>>& heights, int i, int j, vector<vector<bool>>& vis)
//    {
//        if (vis[i][j]) return;
//        vis[i][j] = true;
//
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + i, y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false && heights[x][y] >= heights[i][j])
//                dfs(heights, x, y, vis);
//        }
//    }
//};



//class Solution {
//public:
//    int m, n, k, ret = 0;
//    bool vis[101][101];
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    int movingCount(int _m, int _n, int _k)
//    {
//        m = _m, n = _n, k = _k;
//        dfs(0, 0);
//        return ret;
//    }
//
//    void dfs(int i, int j)
//    {
//        ret++, vis[i][j] = true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + i, y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y] && Check(x, y))
//                dfs(x, y);
//        }
//    }
//
//    bool Check(int x, int y)
//    {
//        int sum = 0;
//        while (x)
//            sum += x % 10, x /= 10;
//        while (x)
//            sum += y % 10, y /= 10;
//        return x <= k;
//    }
//};





class Solution {
public:
    int m, n;
    int dx[8] = { 1, -1, 0, 0, 1, 1, -1, -1 }, dy[8] = { 0, 0, 1, -1, -1, 1, -1, 1 };
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size(), n = board[0].size();
        int i = click[0], j = click[1];
        if (board[i][j] == 'M')
        {
            board[i][j] = 'X';
            return board;
        }
        dfs(board, i, j);
        return board;
    }

    void dfs(vector<vector<char>>& board, int i, int j)
    {
        board[i][j] = 'B';
        int count = 0;
        for (int k = 0; k < 8; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
                count++;
        }

        if (count)
            board[i][j] = '0' + count;
        else
            for (int k = 0; k < 8; k++)
            {
                int x = i + dx[k], y = j + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
                    dfs(board, x, y);
            }

    }
};